package MiddlePractice;

import org.junit.Test;

public class Demo75 {
//	75. 颜色分类
//	给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
//
//	此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
	
	public void sortColors(int[] nums) {
		int[] numMemo = new int[3];
		
		for(int i : nums) {
			numMemo[i]++;
		}
		int last = 0;
		for(int i = 0; i<numMemo[0]; i++, last++) {
			nums[last] = 0;
		}
		
		for(int i = 0; i<numMemo[1]; i++, last++) {
			nums[last] = 1;
		}
		for(int i = 0; i<numMemo[2]; i++, last++) {
			nums[last] = 2;
		}
		
    }
	
	@Test
	public void test_75() {
		int[] in = {2,0,2,1,1,0};
		sortColors(in);
		for(int i:in) {
			System.out.println(i);
		}
	}

}
